Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 77/115

Q: How many properties will an equivalent relationship satisfy?
A. 1
B. 2
C. 3
D. 4
Solution: An equivalent relationship will satisfy three properties – reflexive, symmetric and transitive.
Q: A relation R on a set S, defined as x R y if and only if y R x. This is an example of?
A. reflexive relation
B. symmetric relation
C. transitive relation
D. invalid relation
Solution: A symmetric property in an equivalence relation is defined as x R y if and only y R x.
Q: Electrical connectivity is an example of equivalence relation.
A. true
B. false
C. 
D. 
Solution: Electrical connectivity is reflexive, symmetric and also transitive. Hence, electrical connectivity is an equivalence relation.
Q: What is the worst case efficiency for a path compression algorithm?
A. O(N)
B. O(log N)
C. O(N log N)
D. O(M log N)
Solution: The worst case efficiency for a path compression algorithm is mathematically found to be O(M log N).
Q: Path Compression algorithm performs in which of the following operations?
A. Create operation
B. Insert operation
C. Find operation
D. Delete operation
Solution: Path compression algorithm is performed during find operation and is independent of the strategy used to perform unions.
Q: What is the definition for Ackermann’s function?
A. A(1,i) = i+1 for i>=1
B. A(i,j) = i+j for i>=j
C. A(i,j) = i+j for i = j
D. A(1,i) = i+1 for i<1
Solution: The Ackermann’s function is defined as A(1,i) = i+1 for i>=1. This form in text grows faster and the inverse is slower.
Q: ___________ is one of the earliest forms of a self-adjustment strategy used in splay trees, skew heaps.
A. Union by rank
B. Equivalence function
C. Dynamic function
D. Path compression
Solution: Path compression is one of the earliest forms of self-adjustment used in extremely important strategies using theoretical explanations.
Q: What is the depth of any tree if the union operation is performed by height?
A. O(N)
B. O(log N)
C. O(N log N)
D. O(M log N)
Solution: If the Unions are performed by height, the depth of any tree is calculated to be O(log N).
Q: What is the value for the number of nodes of rank r?
A. N
B. N/2
C. N/2r
D. Nr
Solution: Each node of a rank r is the root of a subtree of at least 2r. Therefore, there are at most N/2r disjoint subtrees.
Q: What is the worst-case running time of unions done by size and path compression?
A. O(N)
B. O(logN)
C. O(N logN)
D. O(M logN)
Solution: The worst case running time of a union operation done by size and path compression is mathematically found to be O(M logN).

You Have Score    /10